Error-correcting codes are used whenever communication over ag15 noisy medium (channel) takes place. Cell phones, computer hard disks, deep-space communication and many other devices communicate over a noisy medium. Error-correcting codes have been widely used and improved since 1948 as the search for optimal error correcting codes continued for decades. The basic problem in decoding is attempting to recover an original transmitted codeword from a received word that is a distorted version of the original codeword. The distortion is introduced by the noisy medium.
Polar codes were introduced in 2009. See, E. Arikan, “Channel Polarization: A method for Constructing Capacity Achieving Codes for Symmetric Binary-Input Memoryless Channels,” IEEE Trans. Inform. Theory, vol. 55, pp. 3051-3073 (2009); E. Arikan and E. Telatar, “On the Rate of Channel Polarization,” in Proc. IEEE Int'l Symp. Inform. Theory, Seoul, South Korea, pp. 1493-1495 (2009)
Polar codes were the first and presently remain the only family of codes known to have an explicit construction (no ensemble to pick from) and efficient encoding and decoding algorithms, while also being capacity achieving over binary input symmetric memoryless channels.). A drawback of existing polar codes to date is disappointing performance for short to moderate block lengths. Polar codes have not been widely implemented despite recognized inherent advantages over other coding schemes, such as turbo codes, because channel polarization remains slow in prior methods.
List decoding was introduced in the 1950s. See, P. Elias, “List decoding for noisy channels,” Technical Report 335, Research Laboratory of Electronics, MIT (1957). List decoding addresses a worst case scenario by outputting a small number of codewords that are a small distance from the code word. List decoding has not been widely used, however. Modern applications of list decoding have sought to reduce worst-case decoding penalties. Successive cancellation list decoding has been applied in to Reed-Muller codes. See, I. Dumer and K. Shabunov, “Soft-decision Decoding of Reed-Muller codes: Recursive Lists,” IEEE Trans. Inform. Theory, vol. 52, pp. 1260-1266 (2006). Reed-Muller codes are structured differently than polar codes and are widely considered in the art to have a different decoding approach. Indeed, Arikan's original paper that presented polar codes emphasized differences between polar codes and Reed-Muller codes. Phrasing of the decoding algorithms in Reed-Muller and Polar codes makes comparison difficult. The present inventors recognized that Arikan's successive cancellation decoding is similar in nature to the successive cancellation decoding of Reed-Muller codes as in Dumer-Shabnov. However, application of successive list decoding as set forth in Dumer-Shavanov would increase complexity of polar decoding to an extent that would make its application impractical. The successive cancellation list decoding in Dumer-Shabunov is also complex, and can lead to Ω(L·n2) complexity. As with prior list decoders, it will also fail to produce a single output, instead producing a small list of candidates without a single, explicit codeword.
The observation that one can reduce the space complexity of successive cancellation decoders for polar codes with hardware architectures to O(n) was noted, in the context of VLSI design, by the present inventors and colleagues in C. Leroux, I. Tal, A. Vardy, and W. J. Gross, “Hardware Architectures for Successive Cancellation Decoding of Polar Codes,” rXiv:1011.2919v1 (2010). This paper does not provide a different decoding approach for polar codes, but provides architectures that can reduce the space complexity for the decoding scheme that was provided by Arikan with the introduction of polar codes.